package org.example.algorithm.dp;

//todo 中心扩展算法、Manacher 算法
public class LongestPalindromeSolution {

    public static void main(String[] args) {
        LongestPalindromeSolution solution = new LongestPalindromeSolution();
        String res = solution.longestPalindrome("daad");
        System.out.println(res);
    }

    /**
     * 动态规划：
     * dp[i][j] = (s[i] == s[j] and (j-i+1<=3 && dp[i+1][j-1]))
     * s = "abcc"
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        if (s.length() <= 1) {
            return s;
        }
        boolean[][] dp = new boolean[s.length()][s.length()];
        int maxLen = 0;
        int start = 0;
        for (int i=s.length()-1;i>=0;i--) {
            for (int j=i;j<=s.length()-1;j++) {
                if ((s.charAt(i) == s.charAt(j)) && ((j-i<=2) || dp[i+1][j-1])) {
                    dp[i][j] = true;
                    if (j-i+1 > maxLen) {
                        maxLen = j-i+1;
                        start = i;
                    }
                }
            }
        }
        return s.substring(start, start+maxLen);
    }

    /**
     * s = "abcdaa"
     * @param s
     * @return
     */
    public String longestPalindrome2(String s) {
        if (s.length() <= 1) {
            return s;
        }
        int max = 1;
        String res=String.valueOf(s.charAt(0));
        for (int i=0;i<s.length();i++) {
            for (int j=s.length()-1;j>=i;j--) {
                if (judgePalindrome(s, i, j)) {
                    if (j-i+1 > max) {
                        max = j-i+1;
                        res = s.substring(i, j+1);
                    }
                }
            }
        }
        return res;
    }

    public Boolean judgePalindrome(String s, int start, int end) {
        if (start == end) {
            return true;
        }
        while (end>=start) {
            if (s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            } else {
                return false;
            }
        }
        return true;
    }
}
